﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Net;
using System.Text.RegularExpressions;

namespace ProjectEulerSolutions.Problems
{
    /*
The following undirected network consists of seven vertices and twelve edges with a total weight of 243.

The same network can be represented by the matrix below.
    	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

However, it is possible to optimise the network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of 93, representing a saving of 243 − 93 = 150 from the original network.

Using network.txt (right click and 'Save Link/Target As...'), a 6K text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.

     * 
     * */
    class Problem107 : IProblem
    {
        public string Calculate()
        {
            int[] original = {  0,  16, 12, 21, 0,  0,  0,
                                16, 0,  0,  17, 20, 0,  0,
                                12, 0,  0,  28, 0,  31, 0,
                                21, 17,	28,	0,	18,	19,	23,
                                0,	20,	0,	18,	0,	0,	11,
                                0,	0,	31,	19,	0,	0,	27,
                                0,	0,	0,	23,	11,	27,	0};


            WebClient wc = new WebClient();
            string input = wc.DownloadString("http://projecteuler.net/project/network.txt");

            original = Regex.Matches(input, "[0-9-]+").Cast<Match>().Select(x => int.Parse(x.Value.Replace('-', '0'))).ToArray();

            int sum = original.Sum() / 2;

            int[] optimized = new int[original.Length];

            int n = (int)Math.Sqrt(original.Length);

            for (int i = 0; i < n; i++)
            {
                while (RemoveGreatest(original, i, n)) ;
            }

            int difference = sum - original.Sum() / 2;

            Console.WriteLine(difference);

            //bool[] connected = new bool[n];
            //connected[0] = true;
            //int current = 0;

            //while (true)
            //{
            //    bool hasDisconnected = false;
            //    for (int i = 0; i < n && !hasDisconnected; i++)
            //        if (connected[i] == false && original[i + current * n] != 0)
            //            hasDisconnected = true;

            //    if (!hasDisconnected)
            //    {
            //        bool foundDisconnected = false;
            //        for (int j = 0; j < n && !foundDisconnected; j++)
            //        {
            //            if (connected[j] == false)
            //                continue;
            //            for (int i = 0; i < n && !foundDisconnected; i++)
            //            {
            //                if (connected[i] == false && original[i + j * n] != 0)
            //                {
            //                    current = j;
            //                    foundDisconnected = true;
            //                }
            //            }
            //        }

            //        if (!foundDisconnected)
            //            break;
            //    }

            //    int next = -1;
            //    int minValue = int.MaxValue;
            //    for (int i = 0; i < n; i++)
            //    {
            //        if (connected[i] == false && original[i + current * n] != 0)
            //        {
            //            if (original[i + current * n] < minValue)
            //            {
            //                minValue = original[i + current * n];
            //                next = i;
            //            }
            //        }
            //    }

            //    connected[next] = true;
            //    optimized[next + current * n] = minValue;
            //    optimized[current + next * n] = minValue;

            //    bool nextConnects = false;
            //    int minIndex = -1;
            //    minValue = int.MaxValue;

            //    for (int i = 0; i < connected.Length; i++)
            //    {
            //        if (i == current || i == next)
            //            continue;

            //        if (connected[i] && original[i + next * n] != 0)
            //        {
            //            nextConnects = true;
            //            if (original[i + next * n] < minValue)
            //            {
            //                minValue = original[i + next * n];
            //                minIndex = i;
            //            }
            //        }
            //    }

            //    current = next;
            //    if (!nextConnects)
            //        continue;

            //    optimized[minIndex + next * n] = minValue;
            //    optimized[next + minIndex * n] = minValue;

            //    RemoveGreatest(optimized, next, n);
            //}

            return difference.ToString();
        }

        bool RemoveGreatest(int[] graph, int vertex, int n)
        {
            //TODO: popravi

            List<int> indices = new List<int>();
            List<int> wasContained = new List<int>();

            indices.Add(vertex);

            int current = vertex;
            int progress = -1;
            do
            {
                bool foundNext = false;
                for (int i = progress + 1; i < n; i++)
                {
                    if (graph[i + current * n] != 0)
                    {
                        if (indices.Count > 1)
                            if (indices.Contains(i) || wasContained.Contains(i))
                            {
                                if (!(indices.Count > 2 && i == vertex))
                                    continue;
                            }

                        foundNext = true;
                        
                        indices.Add(i);
                        progress = -1;
                        current = i;
                        break;
                    }
                }



                if (indices.Count > 1 && !foundNext)
                {
                    progress = indices[indices.Count - 1];
                    wasContained.Add(progress);
                    indices.RemoveAt(indices.Count - 1);
                    current = indices[indices.Count - 1];
                }

            } while (current != vertex && indices.Count > 1);

            int maxIndex = -1;
            int maxValue = 0;

            for (int i = 0; i < indices.Count - 1; i++)
            {
                int value = graph[indices[i] + indices[i + 1] * n];
                if (value > maxValue)
                {
                    maxValue = value;
                    maxIndex = i;
                }
            }

            if (maxIndex != -1)
            {
                graph[indices[maxIndex] + (indices[maxIndex + 1]) * n] = 0;
                graph[indices[maxIndex + 1] + indices[maxIndex] * n] = 0;

                //Console.WriteLine("Removed {0}", vertex);
                return true;
            }

            

            return false;
            //TODO: nadji put koji se vrace do te tocke i makni najveci segment
        }
    }
}
